package com.example.algorithm.tree;

import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;

/**
 * @author : zhy
 * @since : 2022/8/9
 * 由中序和后序遍历序列构造二叉树
 */
public class PerAndAfterToTree {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        int inLen=inorder.length;
        int posLen=postorder.length;
        map=new HashMap<>();
        for(int i=0;i< inLen;i++)
        {
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inLen,postorder,0,posLen);

    }

    private TreeNode findNode(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {

        if(inStart>=inEnd||postStart>=postEnd){
            return null;
        }
        int rootIndex=map.get(postorder[postEnd-1]);
        TreeNode treeNode = new TreeNode(inorder[rootIndex]);
        //标记距离
        int index=rootIndex-inStart;
        treeNode.left=findNode(inorder,inStart,rootIndex,postorder,postStart,postStart+index);
        treeNode.right=findNode(inorder,rootIndex+1,inEnd,postorder,index,postEnd-1);
        return treeNode;
    }

}
